package Lintcode;

import java.util.Scanner;


/**
 * Question: https://www.lintcode.com/zh-cn/problem/ugly-number-ii/
 * Solution: 根据丑数的定义，可知丑数可以由丑数来参数，比如，2 = 1*2, 3 = 1*3, 4 = 2*2， 5 = 1*5, 6 = 2*3 。。。
 * 可见，每个丑数都为之前的丑数推导出来，而最小的丑数为1，之后的丑数都可以从之前的丑数中找一个数，乘上2/3/5得到;
 * 那么问题的关键就成了，如何用已知的丑数中，不重复又刚刚好地推出下一个丑数。
 *
 * 在这个算法中，使用pointer2、 pointer3、 pointer5，指向已经知丑数中的三个（可以指向相同的数），然后每一轮那个这
 * 三个指针指向的数，分别乘上2/3/5，然后选择最小的那个数，作为下一个丑数。被选为丑数的指针向后移一位。这样可以保证，下
 * 一轮最小值的和之前的丑数不重复。
 *
 * Time: 2018/4/29
 * Coder: Ksxy
**/
public class Ugly_number_ii {

    static Scanner scanner = null;
    static {
        scanner = new Scanner(System.in);
    }

    public static void main(String[] args) {
        int n = scanner.nextInt();
        int[] uglyNums = new int[n];
        uglyNums[0] = 1;
        int pointer2 = 0, pointer3 = 0, pointer5 = 0;
        int countOfUglyNumInArray = 1;
        for(; countOfUglyNumInArray < n;) {
            int[] nextUglyNum = {
                    uglyNums[pointer2] * 2,
                    uglyNums[pointer3] * 3,
                    uglyNums[pointer5] * 5
            };
            int min = min(nextUglyNum);
            uglyNums[countOfUglyNumInArray++] = min;
            if(nextUglyNum[0] == min)  pointer2++;
            if(nextUglyNum[1] == min)  pointer3++;
            if(nextUglyNum[2] == min)  pointer5++;
        }
//        System.out.println(uglyNums[n-1]);

        for (int temp : uglyNums) {
            System.out.print(temp+" ");
        }
    }


    public static int min(int[] array){
        if(array.length < 3){
            throw new IllegalArgumentException("array 's length must be 3");
        }
        return array[0] < array[1] ? (array[0] < array[2] ? array[0] : array[2]) : (array[1] < array[2] ? array[1]: array[2]);
    }
}
